package newcoder_exp.justPractise;
import java.util.*;

import org.junit.Test;
public class NC54 {
    public class Solution {
        //找到多组三元组之和为0
        /* 
            输入：
            [-2,0,1,1,2]
            复制
            返回值：
            [[-2,0,2],[-2,1,1]]

            //别妄想了，最高只能O(n^2)
        */
        public ArrayList<ArrayList<Integer>> threeSum(int[] num) {
            ArrayList<ArrayList<Integer>> res = new ArrayList<>();
            if (num == null || num.length < 3) return res;
            int len = num.length;
            Arrays.sort(num);
            /* 
                排序
                先固定左窗口边界(通过遍历i + 1)和target值(-target[i])， 右窗口边界为最右值(hi)，然后在窗口滑动左右边界
                若nums[lo] + nums[hi] == target, 添加到集合；
                若<, 左滑动指针；若>，右移

                注意：两个相邻数的情况应该直接移动过去。
            */
            for (int i = 0; i < len - 2; i++) { //减少判断次数
                if (num[i] > 0) return res;
                if (i >= 1 && num[i] == num[i - 1]) {
                    continue;
                }
                int target = -num[i];
                int lo = i + 1, hi = len - 1;

                while (lo < hi) {
                    
                    if (num[lo] + num[hi] == target) {
                        ArrayList<Integer> list = new ArrayList<>();
                        list.add(num[i]);
                        list.add(num[lo]);
                        list.add(num[hi]);
                        res.add(list);
                        while (lo < hi) {
                            if (num[hi] == num[hi - 1]) hi--;
                            else break;
                        }
                        while (lo < hi) {
                            if (num[lo] == num[lo + 1]) lo++;
                            else break;
                        }
                        lo++;
                        hi--;
                    } else if (num[lo] + num[hi] < target) {
                        lo++;
                    } else {
                        hi--;
                    }
                }
            }
            return res;
        }
    }


    @Test
    public void test() {
        Solution s = new Solution();
        int[] nums = new int[]{-4,-2,1,-5,-4,-4,4,-2,0,4,0,-2,3,1,-5,0};
        System.out.println(s.threeSum(nums));;
    }
/* public class Solution2 {
    public ArrayList<ArrayList<Integer>> threeSum(int[] num) {
        ArrayList<ArrayList<Integer>> res=new ArrayList<>();

        if(num==null || num.length<3){
            return res;
        }
        Arrays.sort(num);// 排序
        for(int i=0;i<num.length-2;i++){
            if(num[i]>0){
                break;// 如果当前数字大于0，则三数之和一定大于0，所以结束循环
            }
            if (i>0 && num[i]==num[i-1]) 
                continue;// 去重
            }
            int L=i+1;
            int R=num.length-1;

            while(L<R){
                int sum=num[i]+num[L]+num[R];
                if(sum==0){
                    ArrayList<Integer> list=new ArrayList<>();
                    list.add(num[i]);
                    list.add(num[L]);
                    list.add(num[R]);
                    res.add(list);

                    while(L<R && num[L]==num[L+1]){
                        L++;
                    }
                    while(L<R && num[R]==num[R-1]){
                        R--;
                    }
                    L++;
                    R--;
                }
                else if(sum>0){
                    R--;
                }
                else if(sum<0){
                    L++;
                }
            }
        }
        return res;
    }
    
} */
}
